package example3;

import common.TreeNode;

import java.util.*;

//236. 二叉树的最近公共祖先
public class LeetCode236 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3,5,1,6,2,0,8,null,null,7,4};
        TreeNode root = constructTree(arr);
//        TreeNode root = buildTree(arr);
//        System.out.println(root);
        System.out.println(new Solution236_1().lowestCommonAncestor(root,new TreeNode(5),new TreeNode(4)).val);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(!isParent(root,p) || !isParent(root,q))  return null;
        if(isParent(root.left,p) && isParent(root.left,q)){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(isParent(root.right,p) && isParent(root.right,q)){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }

    //判断root是否是temp的祖先
    public static boolean isParent(TreeNode root, TreeNode temp){
        if(root == null || temp == null)    return false;
        if(root == temp || root.left == temp || root.right == temp) return true;
        if(root.val == temp.val) return true;
        return isParent(root.left,temp) || isParent(root.right,temp);
    }

    //根据数组创建二叉树============================================================

    //----------------------------------------------------------------------------
    //方法一：基于队列实现

    //ai实现的，基于队列来构造二叉树
    //用队列存储要分配子节点的父节点，存储的父节点是已经分配好的节点，
    //按数组顺序依次为队首节点分配左右子节点，遇到null时跳过子节点创建
    public static TreeNode constructTree(Integer[] array) {
        if (array == null || array.length == 0 || array[0] == null) {
            return null; // 处理空数组或根节点为null
        }

        TreeNode root = new TreeNode(array[0]); // 根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1; // 从数组第二个元素开始
        while (!queue.isEmpty() && index < array.length) {
            TreeNode curr = queue.poll(); // 当前待处理节点

            // 分配左子节点
            if (index < array.length && array[index] != null) {
                curr.left = new TreeNode(array[index]);
                queue.offer(curr.left);
            }
            index++;

            // 分配右子节点
            if (index < array.length && array[index] != null) {
                curr.right = new TreeNode(array[index]);
                queue.offer(curr.right);
            }
            index++;
        }
        return root;
    }
    //----------------------------------------------------------------------------

    //----------------------------------------------------------------------------
    //方法二:递归实现
    public static TreeNode buildTree(Integer[] arr){
        return build(arr,0);    //从根节点0索引开始
    }

    public static TreeNode build(Integer[] arr,int index){
        if(index >= arr.length || arr[index] == null)   return null;
        TreeNode now = new TreeNode(arr[index]);
        now.left = build(arr,index * 2 + 1);
        now.right = build(arr,index * 2 + 2);
        return now;
    }
    //----------------------------------------------------------------------------
}

/**
 * 方法一：递归实现
 */
class Solution236_1{
    private TreeNode ans;

    public Solution236_1(){
        this.ans = null;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return this.ans;
    }

    //这个函数是判断p或q至少有一个是root的后辈节点，如果确定root同时是p和q的祖先，则给ans赋值
    public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        if(root == null)    return false;
        boolean lson = dfs(root.left,p,q);
        boolean rson = dfs(root.right,p,q);
        if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))){
            this.ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
}

/**
 * 方法二：hash表存储所有节点的父节点
 */
class Solution236_2{
    Map<Integer,TreeNode> map = new HashMap<>();
    Set<Integer> set = new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p != null){
            set.add(p.val);
            p = map.get(p.val);
        }
        while(q != null){
            if(set.contains(q.val)) return q;
            q = map.get(q.val);
        }
        return null;
    }

    public void dfs(TreeNode root){
        if(root.left != null){
            map.put(root.left.val,root);
            dfs(root.left);
        }
        if(root.right != null){
            map.put(root.right.val,root);
            dfs(root.right);
        }
    }
}

/*
* Queue的3种入队方法
* add:      队列满时直接抛出IllegalStateException，适合需要快速反馈失败的场景
* offer:    队列满时返回false，高并发或需优雅处理的场景
* put:      队列满时阻塞等待(仅限BlockingQueue)，必须保证任务入队的阻塞场景
* */

